import java.util.Stack;

public class Test {
    public static void main0(String[] args) { //MyStack的main
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);

        int x1 = myStack.pop();
        System.out.println(x1);
        x1 = myStack.pop();
        System.out.println(x1);

        System.out.println(myStack.peek());

    }

    /**
     *  eg1 --- 150. 逆波兰表达式求值
     * @param tokens 表达式
     * @return 表达式的值
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(String x : tokens){
            if(!isOperation(x)){
                stack.push(Integer.parseInt(x)); //将字符转换为整数
            }else{
                int num2 = stack.pop();
                int num1 = stack.pop(); //先弹出两个操作数
                switch(x){
                    case "+":
                        stack.push(num1 + num2); //再将运算好的操作数压栈
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    //判断是否为操作符
    private boolean isOperation(String ch){
        if(ch.equals("+")||ch.equals("-")||ch.equals("*")||ch.equals("/")){
            return true;
        }else{
            return false;
        }
    }

    public static void main1(String[] args) { //eg1的main
        Test test = new Test();
        String[] ret = {"2","1","+","3","*"};
        System.out.println(test.evalRPN(ret));
    }

    /**
     * eg2 -- 20. 有效的括号
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
     * 有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
     * 每个右括号都有一个对应的相同类型的左括号。
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }else{
                //遇到了右括号，但是栈为空，返回false，说明不匹配
                if(stack.empty()){
                    return false;
                }
                //获取右括号
                char ch2 = stack.peek();
                if(ch2 == '[' && ch == ']' || ch2 == '(' && ch == ')' || ch2 == '{' && ch == '}'){
                    stack.pop(); //如果匹配，则将一个左括号出栈，然后再继续匹配
                }else{
                    return false;
                }
            }
        }
        if(!stack.empty()){ //此时已经退出for循环，说明已经遍历完成，此时栈不为空，则不匹配
            return false;
        }
        return true;
    }

    public static void main2(String[] args) { //eg2的main
        Test test = new Test();
        String s = "()[]{}";
        System.out.println(test.isValid(s));
    }

    /** eg3 -- JZ31 栈的压入、弹出序列
     * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
     * 假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
     * 但4,3,5,1,2就不可能是该压栈序列的弹出序列。
     * @param pushA
     * @param popA
     * @return
     */
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushA.length; i++){
            stack.push(pushA[i]);
            while(j < popA.length && !stack.empty() && stack.peek().equals(popA[j]) ){
                //这里的stack类型是Stack<Integer>，Integer范围【-128,127】，如果给一个超出范围的值则会报错，所以这里应该用equals
                stack.pop();
                j++;
            }
        }
        return stack.empty(); //如果是空返回true，如果不为空则返回false
    }

    public static void main3(String[] args) { //eg3
        Test test = new Test();
        int[] arr1 = {1,2,3,4,5};
        int[] arr2 = {4,5,3,2,1};
        System.out.println(test.IsPopOrder(arr1, arr2));
    }
}
